
#include<iostream>

//策略模式
//具有纯虚函数的类：抽象类，不允许实例化对象
class Sort
{
public:
    virtual void sort(int *a,int size) = 0;//纯虚函数

private:
    int a;
};

//未实现父类的纯虚函数，子类仍然是抽象类
class BubbleSort:public Sort
{
public:
    virtual void sort(int *a,int size)//virtual可加可不加
    {
        for (int i=0;i<size;i++)
        {
            for (int j=0;j<size-i-1;j++)
            {
                if (a[j]>a[j+1])
                  std::swap(a[j],a[j+1]);
            }
        }
    }
};

class FastSort
{
public:
    virtual void sort(int *a,int size)
    {
        FSort(int *a,int start,int end);
    }
private:
    void FSort(int *a,int start,int end)
    {
        if (start>=end)
            return;
        int pivot=a[start];
        int i=start,j=end;
        while (i<j)
        {
            while (i<j && a[j]>=pivot)
                j--;
            a[i]=a[j];
            while (i<j && a[i]<=pivot)
                i++;
            a[j]=a[i];
        }
        a[i]=pivot;
        FSort(a,start,i-1);
        FSort(a,i+1,end);
    }
};

void S(Sort *s)
{
    int a[] = {3,1,2};
    s->sort(a,3);
    for (int i = 0;i<3;i++)
        std::cout<<a[i]<<" ";
}

int main ()
{
    //Sort *s= new Sort;   //X
    Sort *s1 = new BubbleSort;
    Sort *s2 = new FastSort;

    S(s1);

    std::cout<<"BubbleSort"<<std::endl;
    return 0;
}   
